from typing import List


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])

        dp = [[0] * n for _ in range(m)]
        for j in range(n):
            dp[0][j] = points[0][j]

        for i in range(1, m):
            for j in range(n):
                dp[i][j] = dp[i - 1][j]

            for j in range(1, n):
                dp[i][j] = max(dp[i][j], dp[i][j - 1] - 1)
            for j in range(n - 2, -1, -1):
                dp[i][j] = max(dp[i][j], dp[i][j + 1] - 1)

            for j in range(n):
                dp[i][j] += points[i][j]

        return max(dp[-1])


if __name__ == "__main__":
    print(Solution().maxPoints(points=[[1, 2, 3], [1, 5, 1], [3, 1, 1]]))  # 9
    print(Solution().maxPoints(points=[[1, 5], [2, 3], [4, 2]]))  # 11

    # 测试用例127/157
    # 11
    print(Solution().maxPoints(points=[[1, 5],
                                       [3, 2],
                                       [4, 2]]))
